package com.example.demo.suanfa_linked;

import org.junit.Test;

/**
 * @program: java_base
 * @description: 反转 单链表
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/07 13:51
 */
public class ReverseListDemo {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            value = data;
        }
    }


    //  head
    //   a    ->   b    ->  c  ->  null
    //   c    ->   b    ->  a  ->  null
    public static Node reverseLinkedList(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            // 当前节点的next
            next = head.next;
            // 当前节点的next
            head.next = pre;
            // 当前节点赋值给 pre，用于挂上前一节点
            pre = head;
            // 用于下次遍历用
            head = next;
        }
        return pre;
    }

    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;

        while (head != null) {
            // 保存下个节点
            next = head.next;
            // 将现在节点的 next 和 last 反转
            head.next = pre;
            head.last = next;
            // 保存现在节点到 pre中，用于下次指向
            pre = head;
            // 指针移动
            head = next;
        }
        return pre;
    }


    @Test
    public void test() {
        Node cur0 = new Node(0);
        Node cur1 = new Node(1);
        Node cur2 = new Node(2);
        Node cur3 = new Node(3);

        cur0.next = cur1;
        cur1.next = cur2;
        cur2.next = cur3;

//        while (cur0 != null) {
//            System.out.println(cur0.value);
//            cur0 = cur0.next;
//        }

        Node node = reverseLinkedList(cur0);
        while (node!=null){
            System.out.println(node.value);
            node = node.next;
        }

    }
}
